package leetcode.editor.cn;


import java.util.*;

//[212]单词搜索 II
public class WordSearchIi212 {
    public static void main(String[] args) {
        Solution solution = new WordSearchIi212().new Solution();

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<String> findWords(char[][] board, String[] words) {
            if (board == null || board.length < 1 || words == null || words.length < 1) return null;

            HashSet<String> res = new HashSet<>();
            //定义字 字典树
            Trie trie = new Trie();
            for (int i = 0; i < words.length; i++) {
                trie.insert(words[i]);
            }

            boolean[][] isUsed = new boolean[board.length][board[0].length];
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                    char c = board[i][j];
                    if (trie.startsWith(String.valueOf(c))){
//                        find(i, j, trie, board, res, "", new boolean[board.length][board[i].length]);
                        find(i, j, trie, board, res, "", isUsed);
                    }
                }
            }
            return new ArrayList<>(res);
        }

        //find 上下左右
        private void find(int i, int j, Trie trie, char[][] board, Set<String> res, String str, boolean[][] isUsed) {
            //查找到，图形的边界。退出。
            if (i < 0 || i >= board.length || j < 0 || j >= board[i].length) return;
            if (isUsed[i][j]) return;//使用过，退出。

            //所有可以拼成的单词的可能。
            str = str + board[i][j];
            if (!trie.startsWith(str)) {
                return;
            }
            if (trie.search(str) && !res.contains(str)) {//当前单词。存在。
                res.add(str);
            }
            isUsed[i][j] = true;
            //上下左右
            //查找更长的单词
            find( i -1, j, trie, board, res, str, isUsed);
            find( i +1, j, trie, board, res, str, isUsed);
            find( i, j-1, trie, board, res, str, isUsed);
            find( i, j+1, trie, board, res, str, isUsed);
            //查找完，回退。
            isUsed[i][j] = false;
        }


        class Trie {
            TrieNode root = new TrieNode();//与上面是相等的，每次，引用this.

            class TrieNode {
                //not have val . son[n] !=null就是 value  son[n] ==null.
                boolean isEnd;
                TrieNode[] son = new TrieNode[26];
            }

            public void insert(String word) {
                if (word == null || word.length() < 1) return;
                TrieNode cur = root;
                char[] chars = word.toCharArray();
                for (int i = 0; i < chars.length; i++) {
                    int sonIndex = chars[i] - 'a';
                    TrieNode sonV = cur.son[sonIndex];
                    if (sonV == null) {
                        cur.son[sonIndex] = new TrieNode();
                    }
                    cur = cur.son[sonIndex];
                }
                cur.isEnd = true;
            }

            public boolean search(String word) {
                TrieNode trieNode = startPrefix(word);
                return trieNode != null && trieNode.isEnd;
            }

            public boolean startsWith(String prefix) {
                return startPrefix(prefix) != null;
            }

            public TrieNode startPrefix(String prefix) {
                if (prefix == null || prefix.length() < 1) return null;
                TrieNode curNode = root;
                char[] chars = prefix.toCharArray();
                for (int i = 0; i < chars.length; i++) {
                    int sonIndex = chars[i] - 'a';
                    TrieNode sonNode = curNode.son[sonIndex];
                    if (sonNode == null) return null;
                    curNode = sonNode;
                }
                return curNode;
            }
        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}